1. Field of the Invention
This invention relates to the field of programmable logic devices and, more particularly, to estimating congestion in programmable logic devices.
2. Description of the Related Art
Programmable logic devices (PLD's), such as field programmable gate arrays (FPGA's), have become increasingly complex and heterogeneous. As such, these devices can include a number of different components that must be interconnected using a variety of different routing resources. Within FPGA's, however, routing resources are finite. As such, competition among components for wiring resources, referred to as congestion, can dictate many aspects of a design for a PLD such as area usage and timing performance.
A user design for a PLD typically is represented as a netlist or other construct specifying logical functions and connections between those functions. A synthesis tool interprets the netlist to create logic blocks and connectivity between the logic blocks. During placement, the logic blocks are assigned to physical locations on the PLD, thereby creating a plurality of sources and loads. Further, the user specified connections between logical functions, now logic blocks, must be routed. Routing user specified connections between logic blocks usually requires a plurality of different wiring resources to complete the connection. This can result in increased competition for selected wiring resources, particularly as regions of the PLD become more populated than others and as user specified timing constraints are taken into consideration.
Accordingly, congestion in a PLD design can manifest itself in several different ways. One way is that as designs become larger, the design may become unroutable. In other cases, the routing may adversely affect the timing characteristics of the PLD design. Still, before congestion can be alleviated or avoided, congestion must be accurately predicted or estimated.
One technique for predicting congestion is to perform a fast estimation of the congestion based upon design placement. Solutions based upon this premise have been proposed for application specific integrated circuits (ASIC's). For example, one approach for estimating congestion within ASIC's has been to use a probabilistic model. The model relies upon two assumptions, particularly that wire used for routing is exactly as long as required and that any two wires crossing can be connected by a via.
Unfortunately, these assumptions do not hold true in the case of FPGA's. FPGA's have wires of fixed, pre-determined length. Further, the connectivity among the wires is limited and fixed. Accordingly, it would be beneficial to provide a technique for estimating congestion in PLD's, and particularly, FPGA devices. It would further be beneficial to provide a model or technique that accounts for specific features of such devices.